#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
    void getNext(int *next, const string &str)
    {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < str.size(); i++)
        {
            while (j > 0 && str[i] != str[j])
            {
                j = next[j - 1];
            }
            if (str[i] == str[j])
            {
                j++;
            }
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s)
    {
        // KMP方法
        int len = s.size();
        vector<int> next(len);
        getNext(&next[0], s);
        cout << "next: ";
        for (auto &elem : next)
        {
            cout << elem << " ";
        }
        cout << endl;
        return next[len - 1] != 0 && (len % (len - next[len - 1]) == 0);
    }
};

int main()
{
    Solution sol;
    cout << sol.repeatedSubstringPattern("abac") << endl;

    return 0;
}